package week02

// 429. N 叉树的层序遍历
// https://leetcode-cn.com/problems/n-ary-tree-level-order-traversal/

// 两种做法
// 1、保存每个点的深度
// 2、双队列

// 保存每个点的深度
func levelOrder(root *Node) [][]int {
	if root == nil {
		return nil
	}

	var ans [][]int
	var queue = []*NodeDepth{newNodeDepth(root, 0)}

	for len(queue) > 0 {
		var nd = queue[0]
		if len(ans) <= nd.depth {
			ans = append(ans, []int{})
		}
		ans[nd.depth] = append(ans[nd.depth], nd.node.Val)
		queue = queue[1:]
		for _, child := range nd.node.Children {
			queue = append(queue, newNodeDepth(child, nd.depth+1))
		}
	}

	return ans
}

func newNodeDepth(node *Node, depth int) *NodeDepth {
	return &NodeDepth{
		node: node,
		depth: depth,
	}
}

type NodeDepth struct {
	node *Node
	depth int
}

// 双队列
func levelOrder2(root *Node) [][]int {
	if root == nil {
		return nil
	}

	var ans = make([][]int, 1)
	var curQueue = []*Node{root}
	var nextQueue []*Node
	var curDepth = 0

	for len(curQueue) > 0 || len(nextQueue) > 0 {
		if len(curQueue) == 0 {
			curQueue = nextQueue
			nextQueue = nil
			curDepth++
			ans = append(ans, []int{})
		}

		var node = curQueue[0]
		ans[curDepth] = append(ans[curDepth], node.Val)
		curQueue = curQueue[1:]
		nextQueue = append(nextQueue, node.Children...)
	}

	return ans
}


type Node struct {
	Val int
	Children []*Node
}